home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / man / node_array.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  3.1 KB  |  84 lines
  1. \bigskip
  2. \bigskip
  3. \bigskip
  4. \bigskip
  5. \bigskip
  6. {\magonebf 5.7 Node and edge arrays (node\_array, edge\_array)}
  7.  
  8. {\bf 1. Definition}
  9.  
  10. An instance $A$ of the parameterized data type $node\_array\<E\>$ 
  11. ($edge\_array\<E\>$) is a partial mapping from the node set (edge set) 
  12. of a (u)graph $G$ to the set of variables of data type $E$, called the 
  13. element type of the array. The domain $I$ of $A$ is called the index set 
  14. of $A$ and $A(x)$ is called the element at position $x$. $A$ is said to 
  15. be valid for all nodes (edges) in $I$. 
  16.  
  17. \def\name {$node/edge\_array\<E\>$}
  18. \def\type {$node/edge\_array$}
  19.  
  20. \bigskip
  21. {\bf 2. Creation}
  22.  
  23. a) \create A {}
  24.  
  25. b) \create A (graph\ G)
  26.  
  27. c) \create A (graph\ G,\ E\ x)
  28.  
  29. d) \create A (graph\ G,\ int\ n,\ E\ x)    
  30.  
  31.  
  32. creates an instance $A$ of type $node\_array(E)$ or $edge\_array(E)$. Variant a)
  33. initializes the index set of $A$ to the empty set, Variants b) and c) 
  34. initialize the index set of $A$ to be the entire node (edge) set of graph $G$,
  35. i.e., $A$ is made valid for all nodes (edges) currently contained in $G$. 
  36. Variant c) in addition initializes $A(i)$ with $x$ for all nodes (edges) 
  37. $i$ of $G$. Variant d) makes $A$ a $node/edge\_array(E)$ valid for up to $n$ 
  38. nodes/edges of $G$, \precond $n \ge |V|$ ($|E|$), this is useful if you want
  39. to use the array for later inserted nodes/edges.
  40.  
  41.  
  42.  
  43. \bigskip
  44. \def\var{$A$}
  45. {\bf 3. Operations}
  46. \medskip
  47.  
  48. \+\op void  init {graph\ G}         
  49.                              {sets the index set $I$ of $A$ to the node (edge)}
  50. \+\nop                       {set of $G$, i.e., makes $A$ valid for all nodes}
  51. \+\nop                       {(edges) of $G$.}
  52. \smallskip
  53. \+\op void  init {graph\ G,\ E\ x}    
  54.                              {makes $A$ valid for all nodes (edges) of $G$ }
  55. \+\nop                       {and sets $A(i) = x$ for all nodes (edges) of $G$}
  56. \smallskip
  57. \+\op void  init {graph\ G,\ int\ n,\ E\ x}  {}
  58. \+\nop                       {makes $A$ valid for at most $n$ nodes (edges)}
  59. \+\nop                       {of $G$ and sets $A(i) = x$ for all nodes (edges)}
  60. \+\nop                       {of $G$. \precond $n \ge |V|$ ($n \ge |E|$). }
  61. \smallskip
  62. \+\opa E\&  {node/edge\ i}                    
  63.                              {access the variable $A(i)$.}
  64. \+\nop                       {\precond $A$ must be valid for $i$.}
  65.  
  66. \bigskip
  67. {\bf 4. Implementation}
  68.  
  69. Node (edge) arrays for a graph $G$ are implemented by \CC vectors and an 
  70. internal numbering of the nodes and edges of $G$. The access operation 
  71. takes constant time, $init$ takes time $O(n)$, where $n$ is the number of 
  72. nodes (edges) currently in $G$. The space requirement is $O(n)$.
  73.  
  74. {\bf Remark}: A node (edge) array is only valid for a bounded number of
  75. the nodes (edges) contained in $G$. This number is either the total number
  76. of nodes of $G$ at the moment of the array creation (variants a) \dots c)) or 
  77. it is explicitely set by the user (variant d)).  Access operations for 
  78. additional later added nodes (edges) are not allowed. Fully dynamic node and
  79. edge arrays can be realized by using hashing arrays, e.g., 
  80. $h\_array(node,\dots)$ (cf.~section~4.5).
  81.  
  82. \vfill\eject
  83.  
  84.